package leetcode.code0424;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution2 implements IDebug {

	public int characterReplacement(String s, int k) {
		// "ADAAACBADDCBCCBA"
		int a = -1, b = -1;// 窗口中两种字符串的编号
		int[] dics = new int[26];// 窗口中a,b的大小
		int ans = 0;// 答案长度
		int l = 0, r = 0;// 窗口左右
		char[] cs = s.toCharArray();
		int len = cs.length;
		while (r < len) {
			int cur = cs[r] - 'A';
			if (cur == a || a == -1) {
				dics[cur]++;
				a = cur;
			} else if (cur == b || b == -1) {
				dics[cur]++;
				b = cur;
			} else {
				// 推掉窗口左侧的字符，直到a,b其中一个为0
				while (dics[a] != 0 && dics[b] != 0) {
					dics[cs[l++] - 'A']--;
				}
				if (dics[a] == 0) {
					a = cur;
				} else {
					b = cur;
				}
				dics[cur] = 1;
			}
			if (a != -1 && b != -1) {
				if (Math.min(dics[a], dics[b]) <= k) {
					ans = Math.max(ans, r - l + 1);
				} else {
					do {
						dics[cs[l++] - 'A']--;
					} while (Math.max(dics[a], dics[b]) > k);
				}
			}
			r++;
		}
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(6, this.characterReplacement("ADAAACBADDCBCCBA", 2));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

		HelpDebug.compare(4, this.characterReplacement("ABAB", 2));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		HelpDebug.compare(4, this.characterReplacement("AABABBA", 1));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
